Operating Systems

1. Deadlock

Deadlock is a situation in operating systems where two or more processes are blocked forever because they are waiting for each other to release resources.

Conditions for Deadlock:

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode (i.e., only one process can use the resource at any given time).

2. Hold and Wait: A process is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes.

3. No Preemption: Resources cannot be preempted (taken away) from processes; they must be released voluntarily.

4. Circular Wait: A set of processes exists such that each process is waiting for a resource held by the next process in the set.

Deadlock Prevention:

Avoiding Circular Wait: One strategy is to impose a total order on all resources and require that processes request resources in an increasing order of enumeration.
Preemptive Resource Allocation: If a process is holding resources and cannot proceed, the system can preempt its resources and give them to other processes.

2. Virtual Memory

Virtual memory allows programs to execute without requiring all of their data to be loaded into physical memory at once. It uses a combination of physical memory (RAM) and disk storage to create the illusion of a large, contiguous block of memory.

Components:

Page Table: Maps virtual memory addresses to physical addresses.
Paging: The memory is divided into fixed-size blocks called pages. When a process accesses a page not currently in memory, a page fault occurs, and the operating system must load the required page from disk.

Page Replacement Algorithms:

LRU (Least Recently Used): Replaces the page that hasn’t been used for the longest period.
FIFO (First In, First Out): Replaces the oldest page in memory.

Example:

If your program accesses memory addresses outside the current physical memory allocation, the OS will trigger a page fault and load the required pages into memory.

3. Semaphores

A semaphore is a synchronization tool used to manage access to shared resources in a concurrent system. It maintains a count that is used to signal whether a resource is available or not.

Types of Semaphores:

Binary Semaphore (Mutex):
- It has two values: 0 or 1.
- Often used for mutual exclusion to ensure that only one process can access a critical section at a time.
Counting Semaphore:
- It can take any non-negative integer value.
- It is useful for managing a set of resources, such as managing access to a pool of database connections.

Operations:

P (Proberen): Decreases the semaphore's value. If the value is less than 0, the process will block until the value is greater than or equal to 0.
V (Verhogen): Increases the semaphore’s value. If there are processes waiting on the semaphore, one of them is unblocked.

Example Code (Binary Semaphore):

let semaphore = 1;  // Semaphore initialized to 1

function P() {
  if (semaphore > 0) {
    semaphore--;  // Enter critical section
  } else {
    console.log("Waiting...");
  }
}

function V() {
  semaphore++;  // Exit critical section
}

Thread Synchronization

Basic Concepts

Thread synchronization ensures orderly access to shared resources in a multi-threaded environment.

Key Aspects

Resource Sharing
- Multiple threads accessing shared resources
- Need for controlled access to prevent data corruption
Critical Section
- Section of code accessing shared resources
- Must be protected from concurrent access
Race Conditions
- Occur when multiple threads access shared data simultaneously
- Result depends on timing of thread execution

Synchronization Mechanisms

Mutex

Binary semaphore
Locks resource for exclusive access

class Mutex {
  constructor() {
    this.locked = false;
  }

  acquire() {
    while (this.locked) {
      // wait
    }
    this.locked = true;
  }

  release() {
    this.locked = false;
  }
}

Semaphores

Counter for resource management
Controls access to finite resources

class Semaphore {
  constructor(initial) {
    this.value = initial;
  }

  wait() {
    while (this.value <= 0) {
      // wait
    }
    this.value--;
  }

  signal() {
    this.value++;
  }
}

Producer-Consumer Problem

Problem Statement

Producers create data items and store in buffer
Consumers remove items from buffer
Need to synchronize access to shared buffer

Components

Buffer
- Shared data structure
- Limited capacity in bounded version
- Unlimited in unbounded version

Producer

Creates items
Adds to buffer when space available

async function produce(buffer, item) {
  await buffer.notFull.wait();
  await buffer.mutex.acquire();
  buffer.add(item);
  buffer.mutex.release();
  buffer.notEmpty.signal();
}

Consumer

Removes items
Waits when buffer empty

async function consume(buffer) {
  await buffer.notEmpty.wait();
  await buffer.mutex.acquire();
  const item = buffer.remove();
  buffer.mutex.release();
  buffer.notFull.signal();
  return item;
}

Implementation

// Mutex implementation
class Mutex {
  constructor() {
    this.locked = false;
    this.waitingQueue = [];
  }

  async acquire() {
    if (!this.locked) {
      this.locked = true;
      return;
    }

    return new Promise(resolve => {
      this.waitingQueue.push(resolve);
    });
  }

  release() {
    if (this.waitingQueue.length > 0) {
      const resolve = this.waitingQueue.shift();
      resolve();
    } else {
      this.locked = false;
    }
  }
}

// Semaphore implementation
class Semaphore {
  constructor(count) {
    this.count = count;
    this.waitingQueue = [];
  }

  async wait() {
    if (this.count > 0) {
      this.count--;
      return;
    }

    return new Promise(resolve => {
      this.waitingQueue.push(resolve);
    });
  }

  signal() {
    if (this.waitingQueue.length > 0) {
      const resolve = this.waitingQueue.shift();
      resolve();
    } else {
      this.count++;
    }
  }
}

// Bounded Buffer implementation
class BoundedBuffer {
  constructor(capacity) {
    this.buffer = [];
    this.capacity = capacity;
    this.mutex = new Mutex();
    this.notFull = new Semaphore(capacity);
    this.notEmpty = new Semaphore(0);
  }

  async produce(item) {
    await this.notFull.wait();
    await this.mutex.acquire();

    this.buffer.push(item);
    console.log(`Produced: ${item}. Buffer size: ${this.buffer.length}`);

    this.mutex.release();
    this.notEmpty.signal();
  }

  async consume() {
    await this.notEmpty.wait();
    await this.mutex.acquire();

    const item = this.buffer.shift();
    console.log(`Consumed: ${item}. Buffer size: ${this.buffer.length}`);

    this.mutex.release();
    this.notFull.signal();
    return item;
  }

  getBufferState() {
    return [...this.buffer];
  }
}

// Helper function to delay execution
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));

// Producer function
async function producer(buffer, id, items) {
  for (const item of items) {
    try {
      await buffer.produce(`P${id}-${item}`);
      await delay(Math.random() * 1000); // Random delay between 0-1000ms
    } catch (error) {
      console.error(`Producer ${id} error:`, error);
    }
  }
  console.log(`Producer ${id} finished`);
}

// Consumer function
async function consumer(buffer, id, count) {
  for (let i = 0; i < count; i++) {
    try {
      await buffer.consume();
      await delay(Math.random() * 2000); // Random delay between 0-2000ms
    } catch (error) {
      console.error(`Consumer ${id} error:`, error);
    }
  }
  console.log(`Consumer ${id} finished`);
}

// Main execution
async function main() {
  const buffer = new BoundedBuffer(5); // Buffer capacity of 5

  // Create multiple producers and consumers
  const producers = [
    producer(buffer, 1, [1, 2, 3, 4, 5]),
    producer(buffer, 2, [6, 7, 8, 9, 10])
  ];

  const consumers = [
    consumer(buffer, 1, 5),
    consumer(buffer, 2, 5)
  ];

  // Wait for all producers and consumers to finish
  await Promise.all([...producers, ...consumers]);
  console.log('All producers and consumers finished');
}

// Run the program
main().catch(console.error);

Common Scenarios

1. Single Producer-Single Consumer

Simplest case
Needs:
- One mutex for buffer access
- Two semaphores (empty, full)

2. Multiple Producers-Single Consumer

Multiple threads adding items
Needs:
- Mutex for producer synchronization
- Buffer bounds checking
- Consumer flow control

3. Single Producer-Multiple Consumers

Multiple threads removing items
Needs:
- Mutex for consumer synchronization
- Empty buffer handling
- Producer flow control

4. Multiple Producers-Multiple Consumers

Most complex scenario
Needs:
- Full synchronization mechanism
- Race condition prevention
- Fair access policies

Implementation Considerations

Buffer Design
- Choose appropriate data structure
- Consider memory constraints
- Handle overflow/underflow
Synchronization
- Prevent deadlocks
- Ensure thread safety
- Maintain data consistency
Performance
- Balance throughput and latency
- Minimize blocking time
- Optimize resource usage

Example Implementation

class BoundedBuffer {
  constructor(size) {
    this.buffer = [];
    this.size = size;
    this.mutex = new Mutex();
    this.notFull = new Semaphore(size);
    this.notEmpty = new Semaphore(0);
  }

  async produce(item) {
    await this.notFull.wait();
    await this.mutex.acquire();

    this.buffer.push(item);

    this.mutex.release();
    this.notEmpty.signal();
  }

  async consume() {
    await this.notEmpty.wait();
    await this.mutex.acquire();

    const item = this.buffer.shift();

    this.mutex.release();
    this.notFull.signal();

    return item;
  }
}

Best Practices

Always Release Resources
- Use try-finally blocks
- Prevent resource leaks
- Handle errors properly
Avoid Nested Locks
- Prevent deadlocks
- Maintain simple locking hierarchy
- Release locks in reverse order
Use Appropriate Mechanisms
- Choose right synchronization tool
- Consider problem requirements
- Balance complexity and needs
Error Handling
- Handle timeout scenarios
- Implement recovery mechanisms
- Log synchronization issues

Common Pitfalls

Deadlock
- Circular resource waiting
- Improper lock ordering
- Resource starvation
Race Conditions
- Unsynchronized access
- Timing-dependent bugs
- Inconsistent state
Priority Inversion
- Lower priority task holds resource
- Higher priority task blocked
- System performance impact
Buffer Problems
- Overflow/underflow
- Memory leaks
- Performance bottlenecks****

1. Deadlock​

2. Virtual Memory​

Components:​

Page Replacement Algorithms:​

Example:​

3. Semaphores​

Types of Semaphores:​

Operations:​

Thread Synchronization​

Basic Concepts​

Key Aspects​

Synchronization Mechanisms​

Producer-Consumer Problem​

Problem Statement​

Components​

Implementation​

Common Scenarios​

1. Single Producer-Single Consumer​

2. Multiple Producers-Single Consumer​

3. Single Producer-Multiple Consumers​

4. Multiple Producers-Multiple Consumers​

Implementation Considerations​

Example Implementation​

Best Practices​

Common Pitfalls​